The present invention relates generally to priority selection circuits and more particularly to combinational encoder circuits that can be utilized with address encoders to generate priority selection addresses.
Priority selection circuits typically receive a number of input signals that can have active and inactive levels. When multiple active input signals are received, the priority selection circuit selects one of the active input signals according to predetermined criteria. For example, input signals may have a particular order, and a priority selection circuit can always select the lowest active input signal in the particular order.
One particular application for priority selection circuits is in content addressable memories (CAMs). A CAM can include an array of CAM cells that compare stored values to an applied comparand value, and in the event there is a match, activate a match indication. A priority selection circuit will select among the multiple match indications to generate single match indication. In CAM applications, priority among multiple match indications can be established according to the physical location of the CAM cells. As just one example, priority can be given to the match indication corresponding to a lowest physical address for the CAM cell array.
In addition to a priority selection circuit, many CAMs will also include an address encoder. An address encoder receives a match signal having priority, and generates an address value from the match signal. The address signal can then be used to access data that corresponds to the match indication. In this way, a CAM will receive a comparand value and generate match signals. The CAM will then determine priority from the match signals, generate an address from a priority match signals, and finally provide output data according to the address.
To better understand the structure and operation of priority encoder circuits and address encoder circuits, a number of conventional circuits will be described.
Referring now to FIG. 8, a conventional priority selection circuit is set forth in a schematic diagram. The conventional priority selection circuit is designated by the general reference character 800, and is shown to include a number of input inverters 802, 804, 806, and 808. Each input inverter (802-808) receives a corresponding input signal, shown as MATCH_IN0-MATCH_IN3. The input signals (MATCH_IN0-MATCH_IN3) of FIG. 8 are active when at a logic low, and inactive when at a logic high. The output of inverter 802 is applied as an input to another inverter 810.
The various input signals are also applied to disable gates, shown as items 812, 814 and 816. The disable gates (812, 814 and 816) will provide a disabling output, which results in an inactive output signal, or alternatively, provide an enabling output which can result in an active output signal. Each disable gate (812, 814 and 816) receives a corresponding input signal by way of an input inverter. In addition, each disable gate (812, 814 and 816) also receives all previous inputs in non-inverted form. Thus, disable gate 812 receives input signal MATCH_IN1 by way of inverter 804 as well as previous input signal MATCH_IN0. Similarly, disable gate 816 receives input signal MATCH_IN3 by way of inverter 808 as well as previous input signals MATCH_IN0, MATCH_IN1 and MATCHxe2x80x94IN2. The disable gate arrangement of FIG. 8 results in the priority selection of input signals (MATCH_IN0-MATCH_IN3) according to order of the signals. If MATCH_IN0 is active (low), the output of disable gates 812, 814, and 816 will all be high, regardless of whether the remaining input signals (MATCH_IN1-MATCH_IN3) are high or low. Similarly, provided MATCH_IN0 is inactive (high), if MATCH_IN1 is active (low), the output of disable gates 814 and 816 will be high, regardless of whether or not the input signals MATCH_IN2 or MATCH_IN3 are high or low. Finally, provided MATCH_IN0 and MATCH_IN1 are inactive (high), if MATCH_IN2 is active (low), the output of disable gate 816 will be high, regardless of whether or not the input signal MATCH 3 is high or low.
The priority selection circuit 800 also includes output gates 818, 820, 822, and 824. The output gates (818-824) each provide a corresponding output signal, shown as MATCH_OUT0-MATCH_OUT3. The outputs gates (818-824) can each receive a xe2x80x9cprior hitxe2x80x9d signal (PRIOR_HIT). The PRIOR_HIT signal indicates whether or not an input signal (not shown) having an even higher priority is active. Thus, when the PRIOR_HIT signal is active (high) the outputs of the output gates (818-824) will be low, regardless of the logic of the input signals (MATCH_IN0-MATCH_IN3).
Also set forth in FIG. 8 is a local hit indicator circuit 826. The prior hit generator 826 generates a local hit signal (LOCAL_HIT). The LOCAL_HIT signal can be used to generate a prior hit signal for subsequent priority selection circuits. The LOCAL_HIT signal will be active whenever one of the input signals (MATCH_IN0-MATCH_IN3) is active. In the particular arrangement of FIG. 8, the LOCAL_HIT signal is active when low, and the local hit indicator circuit 826 includes a NAND gate 828 and an inverter 830. The NAND gate 828 receives each input signal (MATCH_IN0-MATCH_IN3) as an input. The output of NAND gate 828 is inverted by inverter 830 to generate the LOCAL_HIT signal.
While the conventional priority selection circuit of FIG. 8 provides one way of selecting from among four input signals, such an approach may not be desirable due to the number of transistors required to implement the device. This may be particularly true for devices that must establish priority from among a large number of input signals. As just one example, the circuit of FIG. 8 would have to be repeated 32 times for 128 input signals.
Circuit implementations that require a large numbers of transistors can be undesirable as a larger number of transistors can require more area on an integrated circuit. Additional area can translate directly into increased cost for each integrated circuit. Further, the number of interconnections required in a circuit can also impact area, as certain interconnections can require the formation of a contact within the integrated circuit. Accordingly, it is almost always desirable to provide a given functionality with as low a number of transistors as possible.
Referring now to FIG. 9, another conventional priority selection circuit is set forth in a schematic diagram. The priority selection has the same functionality as that set forth in FIG. 8, but reduces transistor count by essentially merging the logic functions of the inverters and disable gates. The circuit of FIG. 9 is described in xe2x80x9cFully Parallel Integrated CAM/RAM Using Preclassification to Enable Large Capacities,xe2x80x9d IEEE Journal of Solid-State Circuits, Vol. 31, No. 5, May 1996, by Schultz and Gulak. Like the example of FIG. 8, the circuits of FIG. 9 can be considered to operate like a carry-look-ahead adder circuit, the LOCAL_HIT signal providing the carry signal. The circuit of FIG. 9 is implemented with complementary metal-oxide-semiconductor (CMOS) gates, and so includes 38 transistors.
To better understand the operation of the conventional priority selection circuits of FIGS. 8. and 9, a truth table is set forth in FIG. 10. Included in FIG. 10 are the various combinations of input values MATCH_IN3-MATCH_IN0 and the resulting output values MATCH_OUT3-MATCH_OUT0. As shown by FIG. 10, for each of the various input signal combinations (MATCH_IN3-MATCH_IN0) only one output signal (MATCH_OUT3-MATCH_OUT0) will be active. The. one active output signal (MATCH_OUT3-MATCH_OUT0) will correspond to the lowest order input signal. For example, when the MATCH_IN3-MATCH_IN0 signal equals xe2x80x9c0000,xe2x80x9d the output signals MATCH_OUT3-MATCH_OUT0 are 0001, reflecting that the lowest active input signal is the MATCH_IN0 signal. When the MATCH_IN3-MATCH_IN0 signal equals xe2x80x9c1001,xe2x80x9d the output signals MATCH_OUT3-MATCH_OUT0 are 0010, reflecting that the lowest active input signal is the MATCH_IN1 signal.
In this way, the conventional priority selection circuits described receive multiple inputs signals, one or more of which can be active, and provides multiple outputs, only one of which is active.
Also set forth in FIG. 10 are address signals X1 and X0 generated from the output signals MATCH_OUT3-MATCH_OUT0. Such signals may be generated by an address encoder circuit (not shown).
Referring now to FIG. 11, a schematic diagram of a third conventional priority selection circuit is set forth. The priority selection circuit of FIG. 11 illustrates the same approach as FIG. 9, but for a case in which eight input signals (MATCH_IN0-MATCH_IN7) are received and eight output signals are provided (MATCH_OUT0-MATCH_OUT7). As illustrated by FIG. 11, as the number of input signals increases, the transistor count for the circuit increases correspondingly. Thus, with conventional approaches, increases in input signal numbers can result in priority selection circuits having increased complexity and size. In FIG. 11, an approach implemented in CMOS includes 92 transistors.
It would be desirable to provide an approach to priority selection circuits that does not require as many transistors as conventional approaches, while at the same time maintaining a relatively fast operating speed.
According to the disclosed embodiments, priority encoding of a number of input signals is accomplished by utilizing a novel combinational encoder with an address encoder. Unlike a conventional priority encoder, which provides a single active output signal in response to various combinations of input signals, the novel combinational encoder provides multiple active output signals for certain combinations of input signals. Such multiple active output signals include one active output signal indicating proper priority, as well as other output signals that can be considered to be extraneous. An address encoder provides a response which essentially xe2x80x9cignoresxe2x80x9d the extraneous active output signals, thereby providing an address value that reflects the proper priority of the input signals.
An advantage of the disclosed embodiments is that a priority encoded address value can be generated by a more compact circuit.
Another advantage of the disclosed embodiments is that a priority encoded address value can be generated with a lower transistor count circuit.
Yet another advantage of the disclosed embodiments is that a compact circuit size can still be maintained as the number of input signals is scaled up.
Yet another advantage of the disclosed embodiments is that an address encoder used to generate the priority encoded address can work with both a conventional priority encoder as well as the disclosed novel combinational encoders. Accordingly, the disclosed combinational encoder may be easily integrated into an existing priority encoding approach.
Yet another advantage of the embodiments is that priority selection can be accomplished according to lowest physical location of an input signal. Thus, the embodiments can be utilized in content addressable memories to establish priority among multiple match signals.
Yet another advantage of the disclosed embodiments is that a more compact priority selection circuit is provided that maintains the relatively fast operating speeds of conventional priority selection circuits.
Yet another advantage of the disclosed embodiments is that a more compact priority selection circuit is provided that provides a local hit indication and also can be disabled by a xe2x80x9cprior hitxe2x80x9d signal. Such features can allow multiple embodiments to used together to establish priority among a relatively large number of input signals.